Search for: All records

We study counting problems for several types of orientations of chordal graphs: source-sink-free orientations, sink-free orientations, acyclic orientations, and bipolar orientations, and, for the latter two, we also present linear-time uniform samplers. Counting sink-free, acyclic, or bipolar orientations are known to be #P-complete for general graphs, motivating our study on a restricted, yet well-studied, graph class. Our main focus is source-sink-free orientations, a natural restricted version of sink-free orientations related to strong orientations, which we introduce in this work. These orientations are intriguing, since despite their similarity, currently known FPRAS and sampling techniques (such as Markov chains or sink-popping) that apply to sink-free orientations do not seem to apply to source-sink-free orientations. We present fast polynomialtime algorithms counting these orientations on chordal graphs. Our approach combines dynamic programming with inclusion-exclusion (going two levels deep for source-sink-free orientations and one level for sinkfree orientations) throughout the computation. Dynamic programming counting algorithms can be typically used to produce a uniformly random sample. However, due to the negative terms of the inclusion-exclusion, the typical approach to obtain a polynomial-time sampling algorithm does not apply in our case. Obtaining such an almost uniform sampling algorithm for source-sink-free orientations in chordal graphs remains an open problem. Little is known about counting or sampling of acyclic or bipolar orientations, even on restricted graph classes. We design efficient (linear-time) exact uniform sampling algorithms for these orientations on chordal graphs. These algorithms are a byproduct of our counting algorithms, but unlike in other works that provide dynamic-programming-based samplers, we produce a random orientation without computing the corresponding count, which leads to a faster running time than the counting algorithm (since it avoids manipulation of large integers). 

Spectral independence is a recently-developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal O(n log n) sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations. Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using L_p-norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, Yin; FOCS’13). The non-linearity of L_p-norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the L_p-analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs. As a main application of our techniques, we consider the random graph G(n, d/n), where the previously known algorithms run in time n^O(log d) or applied only to large d. We refine these algorithmic bounds significantly, and develop fast nearly linear algorithms based on Glauber dynamics that apply to all constant d, throughout the uniqueness regime. 

We study the identity testing problem in the context of spin systems or undirected graphical models, where it takes the following form: given the parameter specification of the model M and a sampling oracle for the distribution \mu_{M^*} of an unknown model M^*, can we efficiently determine if the two models M and M^* are the same? We consider identity testing for both soft-constraint and hard-constraint systems. In particular, we prove hardness results in two prototypical cases, the Ising model and proper colorings, and explore whether identity testing is any easier than structure learning. For the ferromagnetic (attractive) Ising model, Daskalasis et al. (2018) presented a polynomial time algorithm for identity testing. We prove hardness results in the antiferromagnetic (repulsive) setting in the same regime of parameters where structure learning is known to require a super-polynomial number of samples. In particular, for n-vertex graphs of maximum degree d, we prove that if |\beta| d = \omega(\log n) (where \beta is the inverse temperature parameter), then there is no identity testing algorithm for the antiferromagnetic Ising model that runs in polynomial time unless RP = NP. We also establish computational lower bounds for a broader set of parameters under the (randomized) exponential time hypothesis. In our proofs, we use random graphs as gadgets; this is inspired by similar constructions in seminal works on the hardness of approximate counting. In the hard-constraint setting, we present hardness results for identity testing for proper colorings. Our results are based on the presumed hardness of #BIS, the problem of (approximately) counting independent sets in bipartite graphs. In particular, we prove that identity testing for colorings is hard in the same range of parameters where structure learning is known to be hard, which in turn matches the parameter regime for NP-hardness of the corresponding decision problem.